Fonctionnement d'un ordinateur/Les défauts des pipelines de longueur fixe

Avec ce qu'on a dit plus haut, il semblerait que l'implémentation d'un pipeline soit assez simple. Cependant, nous nous sommes limité à des pipelines simples, appelé des pipelines de longueur fixe. Par longueur fixe, on veut dire que toutes les instructions prennent le même nombre d'étage, donc le même nombre de cycles d'horloge. Globalement, cela revient à supposer tous les accès mémoire se font en un seul cycle d'horloge, pareil pour les calculs arithmétiques dans l'ALU, pareil pour les calculs dans l'unité de branchements.

C'est évidemment irréaliste, de tels pipelines ne correspondent pas à des pipelines de processeurs modernes. Les processeurs modernes ont des instructions qui sont plus longues que d'autres : certaines utilisent l'ALU durant un cycle, d'autres pendant 5 cycles, etc. De même, les accès mémoire ne se font pas en un seul cycle en cas de défaut de cache. Les pipeline de ces processeurs sont appelés des pipelines de longueur variable.

Il pourrait paraitre logique de passer directement aux pipelines de longueur variable tout de suite. Cependant, nous allons étudier en détail les pipelines de longueur fixe dans ce chapitre. La raison est que ces pipelines sont beaucoup plus simples que ceux de taille variable. De plus, ce qui sera dit dans ce chapitre vaudra aussi pour les pipelines de longueur variable, alors que les pipelines de longueur variable ont des spécificités bien distinctes, qu'il vaut mieux voir à part. Par exemple, il n'y a pas besoin d’exécution dans le désordre ou de renommage de registres avec un pipeline de longueur fixe.

Tous les pipelines doivent répondre un grand nombre de problèmes assez compliqués. Les 10 chapitres qui vont suivre expliqueront comment ces problèmes sont résolus. Ce chapitre est le moment idéal pour décrire ces problèmes. Les problèmes en question ont tous la même raison : le modèle d’exécution normal suppose qu'une instruction n'est démarrée que lorsque la précédente est terminée, ce qui n'est pas le cas sur un pipeline. Et cela peut causer des problèmes si des instructions consécutives ont des dépendances. Formaliser cette notion de dépendance est très important, et c'est ce qu'on va faire dans la suite. De plus, nous allons voir comment corriger les problèmes liés à ces dépendances. Au passage, ces corrections sont beaucoup plus simples sur les pipelines de longueur fixe.

Les dépendances structurelles

Les dépendances structurelles surviennent quand plusieurs instructions veulent accéder à un circuit du processeur en même temps. Par exemple, deux instructions peuvent ainsi vouloir utiliser l'unité de calcul, accéder à la mémoire simultanément, lire ou écrire dans des registres en même temps. Et à moins que le circuit en question soit conçu pour, une seule instruction aura accès au circuit demandé. Nous allons les voir dans la section suivante.

Introduisons les dépendances structurelles par quelques exemples. Nous allons prendre l'exemple d'un pipeline RISC classique et voir dans quels étages peuvent survenir de telles dépendances. Le pipeline RISC en question supporte des instructions multicycles, sans quoi les dépendances structurelles sont assez limitées. On va voir dans quelles situations vont apparaitre les dépendances structurelles, et on verra aussi que résoudre une dépendance structurelle demande généralement de dupliquer des circuits.

Les accès mémoire ne sont pas censés être source de dépendances structurelles, car le moindre accès mémoire est soit résolu en un cycle, soit bloque tout le pipeline en cas d'accès mémoire. Cependant, il y a une dépendance cachée sur les architecture Von Neumann, qui accèdent à une cache ou une mémoire unique aussi bien pour les instructions que pour les données. A chaque cycle, l'étage de Fetch charge une instruction, pendant que l'étage d'accès mémoire peut faire de même avec une donnée. En clair, il n'est pas rare qu'on ait accès simultané à la mémoire : un pour charger l'instruction, un autre pour charger la donnée.

La solution idéale consiste à dupliquer les circuits. Une solution simple est de passer à une architecture Harvard, avec deux mémoires séparées. Une solution similaire utilise un cache d'instruction séparé du cache de données, ce qui garantit que les deux étages ne se marcheront plus dessus et accéderont chacun à leur mémoire dédiée. D'autres solutions existent, comme utiliser un cache unique mais multiport. Dans tous les cas, on ajoute des circuits pour corriger le problème.

Un autre cas à étudier est l'accès au banc de registres. Dans les pipelines vus précédemment, on y accède en lecture lors de l'étage de chargement des opérandes (ou en parallèle du décodage), avant l'étage d’exécution. Mais on y accède aussi en écriture dans le tout dernier étage. La solution la plus efficace est d'utiliser un cache multiport, avec des ports de lecture séparés du port d'écriture. Il s'agit d'une forme de duplication assez spécifique, où on duplique les ports du banc de registre, pas le banc de registre lui-même.

Les dépendances de contrôle

Les dépendances de contrôle sont liés aux branchements, aux exceptions et aux interruptions. En théorie, les instructions qui suivent un branchement ne doivent pas être chargées ni exécutées tant que le branchement n'est pas terminé. Il faut dire qu'il ne sait pas si le branchement est pris ou non, ni quelle adresse charger suite au branchement. Mais le problème est qu'un branchement met plusieurs cycles à s’exécuter avec un pipeline. Les instructions immédiatement après le branchement sont chargées dans le pipeline à sa suite, à raison d'une instruction par cycle. Ces instructions sont chargées à tort et il faut éliminer ce problème.

Pour corriger le problème, on doit tenir compte de deux cas : est-ce que le branchement est pris ou non. Si le branchement n'est pas pris, aucun problème : les instructions n'ont pas été chargées à tord. Par contre, ce n'est pas le cas pour les branchements pris. Rappelons que certains branchement sont toujours pris : les branchements inconditionnels, les interruptions logicielles. Par contre, les branchements conditionnels peuvent être pris ou non-pris. Les deux cas sont gérés à part, mais pour une raison totalement différente. Le point est que dans un cas, on sait si le branchement est pris dès l'étage de décodage, alors que l'on doit faire un calcul dans l'ALU avec les branchements conditionnels. Les exceptions sont un peu à part.

Les branchements inconditionnels et les interruptions logicielles

Le premier cas est celui des branchements inconditionnels et des interruptions logicielles. Je précise bien logicielles, les exceptions et interruptions matérielles sont gérées autrement. La raison est simple : les interruptions sont des instructions machines au même titre que les branchements normaux.

Branchements inconditionnels et interruptions logicielles sont systématiquement pris, et on le sait dès l'étape de décodage. Le dernier point est important, car il simplifie grandement l'implémentation. Avant l'étape de décodage, aucun registre architectural n'a été modifié, il n'y a pas eu d'accès à la mémoire, l'état du processeur n'a pas changé. Il n'y a donc pas lieu de revenir en arrière et de corriger ce qu'on fait les instructions chargées à tort. Il suffit de ne pas les exécuter.

La solution est donc de ne pas exécuter les N instructions suivantes, N étant le nombre d'instructions chargé à tord. Ce nombre est égal au nombre d'étage avant l'étage de décodage. Les instructions chargées à tord sont remplacées par des NOPs. Évidemment, on perd un peu en performances comparé à un cas idéal, mais n'a pas le choix. Nous verrons dans quelques chapitres que des techniques de prédiction de branchement permettent de résoudre ce problème, mais laissons cela de côté pour le moment. Retenez juste que si on détecte un branchement inconditionnel à l'étape de décodage, on remplace les N instructions suivantes par des NOPs. L'implémentation demande juste un simple compteur et quelques circuits annexes.

Les exceptions précises

Les exceptions matérielles posent le même problème sur les processeurs dotés d'un pipeline. Rappelons qu'une interruption ou une exception matérielle stoppent l’exécution du programme en cours et effectuent un branchement vers une routine d'interruption. Il s'agit de branchements cachés, ce qui fait que le même problème se manifeste.

Et avant que l'exception n'ait été détectée, le processeur a chargé des instructions dans le pipeline alors qu'elles n'auraient pas dû l'être, à savoir les instructions qui sont placées après l'instruction à l'origine de l'exception dans l'ordre du programme. Logiquement, elles n'auraient pas dû être exécutées, vu que l'exception est censée faire brancher le processeur autre part immédiatement. Le problème est que les exceptions et interruptions sont décalées de quelques cycles par rapport à un processeur sans pipeline. On dit que les exceptions sont imprécises. Cela peut poser quelques problèmes à quelques programmes comme les débuggers, même si les cas sont rares.

Exception et pipeline

Pour régler ce petit problème, les concepteurs de processeur ont fait en sorte que le processeur gère lui-même exceptions et interruptions correctement. Ils permettent une gestion des exceptions précises. L'implémentation des exceptions précises dépend de si elles ont lieu avant l'étape de décodage, ou après. En effet, un processeur supporte plusieurs exceptions différentes, qui peuvent être déclenchées à des étages très différents. Certaines sont levées avant l'étage de décodage, comme quand un opcode est invalide, qu'une instruction invalide chercher à s’exécuter, quand la protection mémoire stoppe le chargement d'une instruction, quand on veut exécuter une instruction protégée en espace utilisateur, etc. D'autres sont levées après le décodeur, quand on fait une division par zéro dans l'ALU, quand un accès mémoire à une donnée foire (étage MEM), etc.

Si elles ont eu lieu avant, la situation est particulièrement simple : on fait comme avec les branchements inconditionnels. Les N instructions suivantes sont remplacées par des NOPs, sauf que le nombre N dépend de l'étage qui a levé l'exception. On peut le déterminer à partir de l'exception elle-même, chaque exception est levée à un étage bien précis du pipeline, le nombre de cycle s'en déduit immédiatement.

Le cas où les exceptions sont détectées après l'étape de décodage est tout autre. Dans ce cas, des instructions se sont exécutées à tord. Heureusement, leur résultat n'est enregistré dans les registres qu'à l'étage final du pipeline. Si une exception a lieu, il suffit de ne pas enregistrer les résultats des instructions suivantes dans les registres, jusqu’à ce que toutes les instructions fautives aient quitté le pipeline. Tout étage fournit à chaque cycle un indicateur d'exception, un groupe de quelques bits qui indiquent si une exception a eu lieu et laquelle le cas échéant. Ces indicateurs sont propagés dans le pipeline, ils passent à l'étage suivant à chaque cycle. Une fois arrivé à l'étage d’enregistrement, un circuit combinatoire vérifie ces bits pour détecter si une exception a été levée, et autorise ou interdit l'écriture dans les registres en cas d'exception. Si les écritures sont interdites, elles le sont durant un certain nombre de cycles, dépendant de l'exception levée.

Propagation de l'indicateur d'exception.

De plus, il faut restaurer le program counter pour qu'il pointe vers l’instruction adéquate. Il s'agit de l'instruction qui a déclenché l'exception. Pour cela, même solution : le program counter est propagé dans le pipeline et est restauré en cas d'exception en prenant le program counter disponible à l'étage d'enregistrement.

Les branchements : l'invalidation du pipeline

Pour les branchements, il existe une solution purement logicielle, qui ne demande pas le moindre ajout de matériel. L'idée est de faire suivre les branchements par des instructions qui ne font rien, des NOP (No OPeration) : c'est ce qu'on appelle un délai de branchement. Le processeur chargera ces instructions, jusqu’à ce que l'adresse à laquelle brancher soit connue. Par exemple, si l'adresse à laquelle brancher est connue avec deux cycles d’horloge de retard, il suffit de placer deux NOP juste après le branchement. Mais le nombre de NOP à ajouter dépend du pipeline du processeur, ce qui peut poser des problèmes de compatibilité, sans compter que la perte de performance est notable.

D'autres techniques purement matérielles permettent de corriger les problèmes causés par les branchements, sans recourir à des délais de branchements. Ce qui permet de gagner en performance, tout en corrigeant les problèmes de compatibilité. Leur implémentation dépend d'un point particulier. La dernière instruction à être chargée dans le pipeline le sera en même temps qu'on connait le résultat du branchement. Plus le résultat du branchement est connu tard, plus le nombre d'instructions chargées à tord sera grand. Idéalement, il faudrait connaitre le résultat du branchement très tôt, pour avoir des performances maximales. Et suivant si ce résultat est connu rapidement ou non, l'implémentation est différente.

L'idéal est de connaitre le résultat du branchement à l'étage de décodage, car cela permet une implémentation très efficace. En effet, si on sait qu'un branchement est pris dès l'étape de décodage, on a juste à ne pas exécuter les N instructions suivantes, N étant le nombre d'instructions chargées à tord. Dit comme cela, cela parait bizarre. Le branchement doit s’exécuter pour qu'on connaisse son résultat, et l’exécution a forcément lieu avant l'étape de décodage. Sauf qu'il y a quelques exceptions

• Premier cas : le processeur utilise un registre d'état et calcule les conditions dans l'étage de décodage comme vu dans le chapitre sur le séquenceur. Aussi, les processeurs avec un registre d'état ont un avantage de ce point de vue.
• Une autre solution est celle utilisée sur le pipeline RISC classique. Pour rappel, sur ce pipeline, l'étape de décodage effectue en parallèle la lecture des opérandes dans les registres. Mais ce qu'on n'a pas dit dans le chapitre précédent, c'est qu'elle effectue aussi le calcul des branchements dans une mini-ALU séparée ! Ce faisant, le résultat du branchement est connu dès la fin de l'étape de décodage.

Si le résultat du branchement n'est pas connu à l'étape de décodage, on doit réutiliser la même technique que pour les exceptions précises. L'idée est là aussi de ne pas enregistrer les résultats des instructions fautives. Les instructions chargées à tord ne doivent pas enregistrer leurs résultats dans les registres ou dans la mémoire. Les instructions chargées à tord continuent à se propager dans le pipeline, mais elles échouent à la dernière étape.

Les dépendances de données

Les dépendances de données surviennent quand deux instructions accèdent (en lecture ou écriture) au même registre ou à la même adresse mémoire, mais pas en même temps. Pour le moment, concentrons-nous sur le cas d'un pipeline de longueur fixe. Avec un pipeline de longueur fixe, tout est simple : la plupart des dépendances de données n'existent pas si le pipeline est bien conçu. Le seul type de dépendance qui existe est où une instruction a besoin du résultat d'une instruction précédente pour s’exécuter.

Elles posent problème pour une raison simple : le résultat doit être enregistré dans les registres avant de pouvoir être utilisé comme opérande d'une instruction, mais cette écriture a lieu à la fin du pipeline, quelques cycles après son exécution. Il y a un délai de quelques cycles entre le moment où le résultat est calculé et enregistré. Ainsi, si deux instructions consécutives ont une dépendance de ce type, la seconde lira le registre opérande alors que le résultat n'a pas encore été enregistré dedans.

Les bulles de pipeline

Pour éviter ce genre de problèmes, on a deux grandes solutions. La première solution est que la seconde instruction ne doit pas s’exécuter tant que la première n'a pas enregistré son résultat dans les registres. Elle doit rester dans l'unité de décodage en attendant. L'unité de décodage d'instruction met l'instruction suivante en attente tant que la première n'a pas fini de s’exécuter.

Durant ce temps d'attente, on insère des vides après l'unité de décodage : certains étages seront inoccupés et n'auront rien à faire. Ces vides sont appelés des calages (stall), ou bulles de pipeline (pipeline bubble). De plus, les étages qui précédent l'unité de décodage sont bloqués en empêchant l'horloge d'arriver aux étages antérieurs au décodage.

Pipeline bubble

Le contournement de l'unité de calcul

L'autre solution est celle du contournement. L'idée est de faire en sorte que le résultat d'une instruction disponible rapidement, qu'il soit utilisable directement dans le pipeline, avant son enregistrement dans les registres. Avec la technique du contournement (bypass), le résultat est utilisable en sortie de l'unité de calcul, avant d'être enregistré dans les registres.

Pipeline Bypass

La technique du contournement la plus simple implique uniquement l'unité de calcul. Elle permet à un résultat en sortie de l'unité de calcul d'être réutilisé immédiatement en entrée.

Principe du contournement avec le pipeline RISC classique.

Pour cela, on connecte la sortie de l'unité de calcul sur son entrée si besoin, et on la déconnecte sinon. La connexion/déconnexion se fait avec des multiplexeurs.

Contournement avec des multiplexeurs.

Pour détecter les dépendances, il faut comparer le registre destination avec le registre source en entrée : si ce registre est identique, on devra faire commuter le multiplexeur pour relier la sortie de l'unité de calcul.

Implémentation complète du contournement

Pour améliorer un peu les performances du système de contournement, certains processeurs ajoutent un petit cache en sortie des unités de calcul : le cache de contournement (bypass cache). Celui-ci mémorise les n derniers résultats produits par l’unité de calcul. Le tag de chaque ligne de ce cache est le nom du registre du résultat.

Le contournement de l'unité d'accès mémoire

Il est aussi possible d'envoyer la sortie de l'unité d'accès mémoire sur l'entrée de l'unité de calcul. La seule complexité est de déterminer si la donnée lue est disponible, et de prévoir si l'instruction de calcul qui consomme cette donnée est disponible. Les processeurs modernes n'implémentent pas forcément cette forme de contournement, car prédire la durée d'une instruction mémoire est compliqué.

Mais sur les processeurs où l'accès mémoire se fait en un cycle en cas de succès de cache, les choses sont plus simples. Au pire, un défaut de cache cause un pipeline stall, une bulle de pipeline, ce qui fait que l'instruction de calcul consommatrice sera figée en entrée de l'ALU. Le câblage du processeur est alors plus complexe. Et surtout, cette forme de contournement a un effet très différent suivant le pipeline.

Si on a une unité d'accès mémoire séparée de l'unité de calcul, tout va bien, tout se passe comme avec le contournement de l'unité de calcul, les circuits sont très similaires et demandent juste un multiplexeur bien placé. La sortie de l'unité d'accès mémoire est connectée à une entrée du multiplexeur, l'autre entrée est connectée aux registres. La sortie du multiplexeur est connectée à l'ALU. La commande du multiplexeur est effectuée par les signaux de commande adéquats provenant du séquenceur.

Mais sur le pipeline RISC classique, où l'unité de calcul et l'unité mémoire sont placées en série, les choses sont plus compliquées. En effet, il y a deux cycles de différence entre l'entrée de l'unité de calcul et la sortie de l'unité mémoire. La conséquence est que la donnée lue est disponible deux cycles après l'entrée dans l'ALU, alors que l'instruction de calcul démarre un cycle après l'instruction d'accès mémoire. Il y a un cycle de différence qui fait que le résultat est connu un cycle trop tôt.

Data Forwarding (Two Stage, error)

La solution est double. Déjà, il faut retarder le résultat d'un cycle d'horloge, typiquement en ajoutant un registre avant le multiplexeur. Ensuite, il faut insérer une bulle de pipeline avant de démarrer l'instruction de calcul. En clair, on économise un cycle au lieu de deux.

Data Forwarding (Two Stage)